package 树;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 好叶子节点的数量.java
 * @Description TODO
 * @createTime 2020年10月10日 15:36:00
 * 给你二叉树的根节点 root 和一个整数 distance 。
 *
 * 如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
 *
 * 返回树中 好叶子节点对的数量 。
 *
 *  
 *
 * 示例 1：
 *
 *  
 *
 *
 *
 * 输入：root = [1,2,3,null,4], distance = 3
 * 输出：1
 * 解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
 *
 *
 * 思路1：每个非叶子节点保存其到每个叶子节点的距离 然后和那个整数进行比较
* 用一个数组来记录该节点到每个叶子节点的距离 从底往上 每往上一次就 用for循环为数组的每个元素+1
 * 来记录数据的时候一定要分左右节点 最后返回的时候 把左右节点整合返回
 * 凡是从底到顶 携带数据的都是通过这种方式
 * 1. int leftHeight = maxDepth(root.left);
 * //            int rightHeight = maxDepth(root.right);
 * //            return Math.max(leftHeight, rightHeight) + 1;
 * 影响的数据通过return来增添
 *
 * 2. List<Integer> left=post(root.left);
 *         List<Integer> right=post(root.right);
 *
 *         for(int i=0;i<left.size();i++){
 *             left.set(i,left.get(i)+1);
 *         }
 *
 *         for(int i=0;i<right.size();i++){
 *             right.set(i,right.get(i)+1);
 *         }
 */
public class 好叶子节点的数量 {
//这题和 二叉树的最大深度类似
//    int result;
//
//    public int countPairs(TreeNode root, int distance) {
//        post(root, distance);
//
//        return result;
//    }
//
//    public List<Integer> post(TreeNode root, int distance) {
//        if (root == null) {
//            return new ArrayList<>();
//        }
//        if (root.left == null && root.right == null) {
//            List<Integer> list = new ArrayList<>();
//            list.add(0);
//            return list;
//        }
//        List<Integer> left = post(root.left, distance);
//        List<Integer> right = post(root.right, distance);
//        for (int i = 0; i < left.size(); i++) {
//            left.set(i, left.get(i) + 1);
//        }
//        for (int i = 0; i < right.size(); i++) {
//            right.set(i, right.get(i) + 1);
//        }
//        for (Integer i : left) {
//            for (Integer j : right) {
//                if (i + j <= distance) {
//                    result++;
//                }
//            }
//        }
//        List<Integer> list = new ArrayList<>(left);
//        list.addAll(right);
//        return list;
//    }

}
